package com.leetcode.专项突破.二叉树;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-04-09 16:32
 */
public class PreorderTraversal {


  static
  class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {
//      List<Integer> answer = new ArrayList<>();
//      preorderTraversalWithRecursion(root, answer);
//      return answer;
      return preorderTraversalWithStack(root);
    }

    private void preorderTraversalWithRecursion(TreeNode root, List<Integer> answer) {
      if (root == null) {
        return;
      }
      answer.add(root.val);
      preorderTraversalWithRecursion(root.left, answer);
      preorderTraversalWithRecursion(root.right, answer);
    }

    private List<Integer> preorderTraversalWithStack(TreeNode root) {
      List<Integer> answer = new ArrayList<>();
      if (root == null) {
        return answer;
      }

      Deque<TreeNode> stack = new ArrayDeque<>();
      stack.push(root);

      while (!stack.isEmpty()) {
        root = stack.pop();
        answer.add(root.val);
        if (root.right != null) {
          stack.push(root.right);
        }
        if (root.left != null) {
          stack.push(root.left);
        }
      }

      return answer;
    }

  }


}
